/**
 * 最长公共子序列的贪心算法解法
 * @param wordX 字符串X
 * @param wordY 字符串Y
 */
export function lcs(wordX: string, wordY: string, m = wordX.length, n = wordY.length): number {
    if (m === 0 || n === 0) {
        return 0;
    }

    if (wordX[m - 1] === wordY[n - 1]) {
        return 1 + lcs(wordX, wordY, m - 1, n - 1);
    } else {
        // 谁的最长公共子序列最长就取谁，跟动态规划的递归写法很像
        const a = lcs(wordX, wordY, m, n - 1);
        const b = lcs(wordX, wordY, m - 1, n);
        return a > b ? a : b;
    }
}
